One of the most relevant and critical issues in digital communication relates to the design of efficient decoding algorithms. In order to recover useful and intended information, specific digital processing is needed at the receiver side. This applies to all communication systems covering both single and multiple transmissions such as multi-users and multiple-antenna communication systems as MIMO (Multiple-Input Multiple-Output).
Specifically, multiple antenna technologies play a fundamental role in the design of many wireless communication systems due to their potential to increase the spectral efficiency and the transmission data rates. Several wireless standards such as the LTE and the WiMAX (IEEE 802.16) have incorporated MIMO communications to enhance the network performance and take advantage of the diversity brought by multiple antennas. In such systems, the digital signals are sent from a transmitter device to a receiver device in an encoded form through a transmission channel. The receiver device is configured to decode the received signal from the channel output so as to access the data. A main challenge in such systems is the design of efficient and low-complexity detectors.
In particular, the transmission channel can be noisy which may involve a disruption of the received signals. Such disruption can be limited at the decoding side by using a suitable decoding technique to properly decode the received signal. A known decoding technique is the Maximum Likelihood (ML) decoding technique according to which the receiver device is configured to estimate the likeliest candidate signal, given the observed received signal.
Optimal ML decoding technique relies on counting all the possible transmitted signals (also referred to as “candidate signals”), and selecting the likeliest signal according to selection criteria, such as the Euclidean distance between the observed signal received and the candidate signals.
However, such an exhaustive count is costly in terms of time and resources, and can be difficult to implement in real-time applications. Indeed, the number of candidates, and therefore the complexity of the decoder, exponentially increases with the length of the digital signal. For practical implementations, alternative lattice decoding algorithms have been proposed to properly decode the received signal while considering the decoder complexity, such as the Sphere Decoder (E. Viterbo and J. Boutros. A universal lattice code decoder for fading channels. IEEE Transactions on Information Theory, 45(5):1639-1642, July 1999) or the Schnorr-Euchner decoder (C. P. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. In Math. Programming, pages 181-191, 1993). This class of decoders is particularly adapted to wireless communications involving both single and multiple antennas as well as to optical communications.
Such decoding algorithms implement optimal ML criterion. However, they increase the complexity when the constellation size or the number of antennas increases.
In other existing approaches, suboptimal low-complexity decoders such as the ZF, the ZF-DFE and the MMSE (K. R. Kumar, G. Caire, and A. L. Moustakas. Asymptotic performance of linear receivers in mimo fading channels. IEEE Transactions on Information Theory, 55(10):4398-4418, October 2009) are implemented. Such decoders are generally used in practical systems presenting limited computational capabilities.
Still other decoding techniques have been proposed such as sequential decoding techniques which are based on a tree representation of the ML optimization problem (decoding tree) and on a tree search. In such decoding tree, each path from the root node to a leaf node is a possible transmitted signal. There exist three main tree-search strategies: the breadth-first, the depth-first and the best-first strategy. Nodes in the search tree correspond to different values taken by the decoded symbols and each path from the root node to a leaf node is a possible transmitted signal.
Sequential decoding techniques take into account a cost (or metric) constraint in order to determine a single candidate path inside a decoding tree by assigning a cost to each current node, such as the Euclidean distance between the signal received and the path between the root node and the current node. The search tree is no longer binary and contains the different possible values of the information symbols.
According to a “breadth-first” tree search strategy, the search starts with the root node and extends all its child nodes existing at the following level. For each explored node, the search algorithm extends successively all its child nodes until reaching leaf nodes. With such an approach, at a given level i, all the nodes are explored before moving to the level i−1 of the tree in such a way that all linear combinations s(i)=(sn, sn-1, . . . , si) are computed (i.e. the search over the tree is made in the width sense). The “breadth-first” strategy thus implements an exhaustive search over the tree.
Another exhaustive tree search strategy called the “Depth-First strategy” and generally used in the Sphere Decoders and Schnorr-Euchner decoders, starts from the root node and explores the first child node sn, then its nearest child node Sn-1, and so on until reaching a leaf node s1. Given this first path found, the search proceeds by returning back to the level 2 in the tree and explores the neighbor of the already explored node s2. After finding all the possible paths and computing their relative cumulated weights, the shortest path is output.
The “Best First strategy” is still another tree search strategy which corresponds to an optimized version of the Breadth-First strategy. The search strategy is based on exploring only paths having smallest weights than a predefined weight constraint. Starting from the root node, the algorithm explores all child nodes sn and keeps only the nodes having the weights that satisfy the constraint by storing them in a stack. The child nodes of the top node in the stack are then generated and their cumulated weights are computed. The explored nodes are searched according to their weights and only the nodes with the least cumulated weights are kept. The search is continued until finding a leaf node and the optimal path s(1)=(sn, sn-1, . . . , s1) is returned. By maintaining only the nodes having low weights compared to a given cost constraint, the search complexity is reduced.
Stack decoders were originally used to decode convolutional codes transmitted over discrete memoryless channels. Later on, they were rediscovered and adapted for ML detection in MIMO systems as disclosed in “A unified framework for tree search decoding: rediscovering the sequential decoder”, Arul Murugan et al., “IEEE transaction on information theory”, volume 52, pages 933-953, March 2006.
Sequential decoding can be implemented in a Fano decoder (R. Fano. A heuristic discussion of probabilistic decoding. IEEE Transactions on Information Theory, 9(2), pages 64-74, April 1963.) or in a stack decoder, delivering a hard estimation of the signal transmitted, i.e. a binary estimation, as described in particular in the article “A fast sequential decoding algorithm using a stack” (F. Jelinek, “IBM Journal Research Development”, volume 13, pages 675-685, November 1969).
To generate the decoding tree according to the Best-First tree search strategy, the stack decoder starts from the root node sroot, and generates at each level all the child nodes corresponding to the detected symbols. The respective weight of each child node is further computed. The child nodes are then stored in a stack in an increasing order of their weights such that the node in the top of the stack has the least metric. The stack is then reordered and the same processing is repeated until a leaf node reaches the top of the stack. The path corresponding to a leaf node represents the ML solution. The stack decoder can thus find the closest vector to the received signal according to the ML criterion.
The Stack decoder has a lower complexity than the Fano decoder (as demonstrated in the article “A fast sequential decoding algorithm using a stack”, F. Jelinek, “IBM Journal Research Development”, volume 13, pages 675-685, November 1969). However, for an increasing constellation size and a high number of antennas, the stack decoding technique requires a high computational complexity.
In order to reduce this complexity, another decoding technique referred to as the Spherical-Bound Stack decoder (SB-Stack) has been proposed in the article by G. R. Ben-Othman, R. Ouertani, and A. Salah, entitled “The Spherical Bound Stack Decoder”, In Proceedings of International Conference on Wireless and Mobile Computing, pages 322-327, October 2008. The SB-stack approach combines the Stack search strategy with the Sphere Decoder search region: The ML solution is sought inside a sphere centered at the received point. Using this approach, the SB-stack decoder achieves lower complexity than the Spherical decoder. However, although the SB-stack decoder offers lower complexity than the Sphere Decoder, its implementation in practical systems requires high storage capacities.
Thus, optimal decoding tree generation methods and systems with a reduced decoding complexity are needed.